package datasorter;

import org.apache.log4j.Logger;

/**
 * 
 * @author Lester
 * 
 */
public class MergeSort extends DataSorter<Integer> {
	private static final Logger log = Logger.getLogger(MergeSort.class);
	Integer[] tempArray ;
	public  Integer[] sort(Integer[] data) {
		if (data == null)
			return null;
		if (data.length == 0 || data.length == 1)
			return data;
		tempArray = new Integer[data.length];
		log.info("Extra memory-"+tempArray.length);
		sort(data, 0, data.length - 1);
		return data;
	}

	public Integer[] sort(Integer[] data, SortType type) {
		if (data == null)
			return null;
		if (data.length == 0 || data.length == 1)
			return data;
		if (SortType.DESC.equals(type)) reverse(data);
		return data;
	}

	/**
	 * method that makes recursive calls.
	 * 
	 * @param data input array of data.
	 * @param startPos left-most index of the array.
	 * @param endPos right-most index of the array.
	 */
	private void sort(Integer[] array, int startPos, int endPos) {
			if (startPos < endPos) {
			int middle = startPos + (endPos - startPos) / 2;
			sort(array, startPos, middle);
			sort(array, middle + 1, endPos);
			merge(array, startPos, middle, endPos);
		}
	}

	/**
	 * method that merges two sorted halves of a array.
	 * 
	 * @param data  input array of data.
	 * @param low left-most index of the array.
	 * @param middle the index of the start of the second half.
	 * @param high right-most index of the array.
	 */
	private  void merge(Integer[] data, int low, int middle, int high) {
		for (int k = low; k <= high; k++) {
			tempArray[k] = data[k];
		}
		int i = low;
		int j = middle + 1;
		for (int k = low; k <= high; k++) {
			if (i > middle) {
				data[k] = tempArray[j++];
			} else if (j > high) {
				data[k] = tempArray[i++];
			} else if (tempArray[j] < tempArray[i]) {
				data[k] = tempArray[j++];
			} else {
				data[k] = tempArray[i++];
			}
		}
	}
}